No part of this work may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopying, recording, or by any information storage and retrieval system, without permission in writing from the publisher. However, you are permitted to make copies of this work, printed or otherwise, as long as said copies are for your personal use only.
-------
Recursion is a process in which you have an event or action take place inside of itself. A good example of this is when you point a video camera into a monitor that is displaying what the video camera is seeing. What you get is a series of pictures within pictures, that seem to stretch to infinity. Recursion becomes useful when you have a given problem that desires an unknown quantity of actions, where the actions are all similar in nature.
Here is a typical problem: You are the security guard in an office building with 12 floors. One of your assignments every night is to make sure all the doors are locked on each floor. You are required to fill out a form for each main door you find unlocked. If you find an unlocked door, you will need to go into the room and make sure that any doors within the room are locked. For each of the doors within the room you find unlocked, you will need to go into the subroom and perform the same check, until you have exhausted all the possibilities. See the recursion? You are performing the same task, but you do not know how many times you will need to perform it, nor do you know how many levels you will need to venture in order to check every possible door. And each night will be a different experience, what with different people forgetting to lock their doors.
I, Robot
If you could design a robot to perform the 12 floor check, you could program it many different ways. A simple approach would be to set up a table or chart corresponding to the number of floors, and for each floor, the number of doors and subdoors. If each floor has 12 doors, then you need to know about 144 doors total. However, if each door leads to a room that has another two doors, you're up to 288 doors. And if each subroom has another door or two, you've got a lot of doors to keep track of. So, your poor robot would have to keep track of all of these doors and would need fairly extensive and intimate knowledge of the floorplan for the office building. Also, if any rooms are added or removed, your robot will have to be reprogrammed.
To approach this problem recursively, teach your robot about floors and doors. Don't tell your robot how many doors to expect on each floor, just that there are an unknown number, and within each room, an unknown number of additional possibilities. Also teach your robot how to take the elevator to the next floor, and once it can go no further, to return to the ground floor. OK, what does this look like to your robot? Here is an example piece of pseudo-code that tells the robot to check each room within a room, ad infinitum.
Program "Check Room"
Go into room
While there are still unchecked doors
Check a door
If a door is unlocked
Do Program "Check Room"
End If
End While
You'll note that the program "Check Room" will call itself when faced with an unlocked door. That is the heart of recursion. It will do this as many times as necessary, until there are no more doors to check, and then back itself out of each room.
Problems
There are some problems with recursion. If you are trying to develop a speedy program, recursion may slow things down a bit, because of the level of complexity you force upon the computer. Also, if your nesting of rooms becomes too deep, the robot may forget how to navigate its way back -- also known as too many items on the stack.
MicroPhone Example
So, now you want to make use of recursion in MicroPhone. First, ask yourself, what would I use it for? What situation calls out for recursion? Well, one that comes to mind is getting a list of all the files on a given hard disk. You have folders within folders within folders, and each of these folders may or may not contain files.
The example scripts in the Recursion Simplified settings document demonstrate the power of recursion. Try them out, print them, study them, and you'll soon be on your way to writing recursively!
